/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequence = function (s) {
  // 预处理：存储每个字符的所有出现索引（数组形式）
  const charIndices = new Array(26).fill(0).map(() => []);
  for (let i = 0; i < s.length; i++) {
    const charCode = s.charCodeAt(i) - "a".charCodeAt(0);
    charIndices[charCode].push(i);
  }

  let result = 0;

  // 枚举 26 个小写字母（作为首尾字符）
  for (let c = 0; c < 26; c++) {
    const indices = charIndices[c];
    // 若该字符出现次数少于 2 次，无法形成首尾对
    if (indices.length < 2) continue;
    // 取第一次和最后一次出现位置
    const left = indices[0];
    const right = indices[indices.length - 1];
    // 中间无字符，跳过
    if (left >= right - 1) continue;

    // 统计中间区间 [left+1, right-1] 中不同字符的个数
    const uniqueChars = new Set();
    for (let i = left + 1; i < right; i++) {
      uniqueChars.add(s[i]);
    }
    // 累加不同中间字符的个数
    result += uniqueChars.size;
  }

  return result;
};
